class UnionFindSet
{
public:
	UnionFindSet(size_t size) :_set(size, -1) {}

	int FindRoot(int x)
	{
		if (_set[x] >= 0) _set[x] = FindRoot(_set[x]);

		if (_set[x] < 0)
			return x;
		else
			return _set[x];
	}




	bool InSet(int x, int y) { return FindRoot(x) == FindRoot(y); }

	void Union(int x, int y)
	{
		int rootx = FindRoot(x);
		int rooty = FindRoot(y);

		if (abs(_set[rootx]) < abs(_set[rooty]))
			swap(rootx, rooty);

		_set[rootx] += _set[rooty];
		_set[rooty] = rootx;
	}

	size_t SetCount()
	{
		size_t num = 0;
		for (size_t i = 0; i < _set.size(); i++)
			if (_set[i] < 0)
				num++;
		return num;
	}

private:
	vector<int> _set;
};

void TestUnionFindSet()
{
	UnionFindSet ufs(10);
	ufs.Union(8, 9);
	ufs.Union(7, 8);
	ufs.Union(6, 7);
	ufs.Union(5, 6);
	ufs.Union(4, 5);

	ufs.FindRoot(6);
	ufs.FindRoot(9);
}

//class _UnionFindSet
//{
//public:
//	_UnionFindSet(size_t size) :_set(size, -1) {}
//
//	int FindRoot(int x)
//	{
//		if (_set[x] >= 0) _set[x] = FindRoot(_set[x]);
//
//		if (_set[x] < 0)
//			return x;
//		else
//			return _set[x];
//	}
//
//	void Union(int x, int y)
//	{
//		int rootx = FindRoot(x);
//		int rooty = FindRoot(y);
//
//		if (rootx != rooty)
//		{
//			_set[rootx] += _set[rooty];
//			_set[rooty] = rootx;
//		}
//	}
//
//	size_t SetCount()
//	{
//		size_t num = 0;
//		for (size_t i = 0; i < _set.size(); i++)
//			if (_set[i] < 0)
//				num++;
//		return num;
//	}
//
//private:
//	vector<int> _set;
//};
